perm filename A68.TEX[106,RWF] blob
sn#807783 filedate 1985-09-20 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00002 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 \magnification\magstephalf
C00005 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
January\or February\or March\or April\or May\or June\or
July\or August\or September\or October\or November\or December\fi
\space\number\day, \number\year}
\baselineskip 14pt
\parskip 6pt
\rm
\line{\sevenrm a68.tex[106,phy] \today\hfill}
\bigskip
{\narrower\smallskip\noindent
{\bf Exercise: Dynamic Programming.}
\vskip 2truein
\noindent
We are given a sequence of points by their coordinates. We want to find,
as shown above, a small number of straight lines that closely fit the points.
If the points have coordinates $(x↓i,y↓i)$ ($1≤i≤n$), we can find the best
single line by this algorithm:
Compute
$$\eqalign{SX&=\sum x↓i\cr
SY&=\sum y↓i\cr
SXX&=\sum x↓i↑2\cr
SXY&=\sum x↓iy↓i\cr
SYY&=\sum y↓i↑2\cr
\vdots\cr}$$
The error minimized is measured by the sum of the squares of the distances
of the lines from the points, which is \dots .
Develop an algorithm which, for each $N$ up to (say)~10, finds the best
broken line of $N$~segments, in the sense of minimizing the sum of the
squares of the distances from a point to a line segment.
\smallskip}
\bigskip
\line{\copyright 1985 Robert W. Floyd\hfill}
\line{First draft (not published) March 26, l985.\hfill}
\bye